'''
Created on 2024年7月29日

@author: Administrator
'''
def compute_lps(pattern,M):
    
    lps = [0]*M
    length = 0
    i = 1
    
    while i<M:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length-1]
            else:
                lps[i] = 0
                i += 1
#                 -~i      
    
    return lps


def KMP_search(pat,txt):    
    M = len(pat)
    N = len(txt)
    print(pat)
    lps = compute_lps(pat,M)
    print("lps:",lps)
    
    i = 0
    j = 0 
    while i<N:
        if pat[j] == txt[i]:
            i += 1
            j += 1
        if j == M:
            print(f"Found pattern at index {i-j}")
            j = lps[j-1]
        elif i < N and pat[j] != txt[i]:
            if j != 0:
                j = lps[j-1]
            else:
                i += 1
                
            
        
    return i-j


def get_next(pattern):
    
    print("pattern:",pattern)
    
    j = -1
    i = 0
    M = len(pattern)
    n = [-1]*M
    
    while i < M-1:
        if j == -1 or pattern[i] == pattern[j]:
            j += 1
            i += 1
            n[i] = j
        else:
            j = n[j]
    
    return n

def search(pattern,text):
    
    n = get_next(pattern)
    
    M = len(pattern)
    N = len(text)
    
    i = 0
    j = 0
    
    while i < N and j < M:
        if j == -1 or text[i] == pattern[j]:
            i += 1
            j += 1
        else:
            j = n[j]
    
    if j == M:
        return i-j
    else:
        return -1        


if __name__ == "__main__":
    
    print([0]*8)
    i = 11
    print(-~i)
    
    txt = "ABABDABACDABABCABAB"
    pat = "ABABD"
    KMP_search(pat, txt)
    txt = "ABABDABACDABABCABAB"
    pat = "ABABCABAB"
    KMP_search(pat, txt)

    i = 1
    j = 0
    pat = 'aaaaab'
    M = len(pat)
    lps = [0]*M
    while i < M:
        if pat[i] == pat[j]:
            j += 1
            lps[i] = j
            i += 1
        else:
            if j != 0:
                j = lps[j-1]
            else:
                lps[i] = 0
                i += 1
    print(pat)
    print("lps:",lps)
    
    print(compute_lps('ababac', 6))
    print(compute_lps('aaaaaa', 6))
    print(compute_lps('aaaaac', 6))
    
    print(get_next('ababac'))
    print(get_next('aaaaab'))
    
    
    txt = "ABABDABACDABABCABAB"
    pat = "ABABD"
    print(search(pat, txt))
    txt = "ABABDABACDABABCABAB"
    pat = "ABABCABAB"
    print(search(pat, txt))
    
    
        